//
// Created by 高森森 on 2022/2/17.
//

#ifndef LEETCODE_SOLUTION53_H
#define LEETCODE_SOLUTION53_H

#include <iostream>
#include <string.h>
using namespace std;

#include <vector>
#include <unordered_set>
#include <queue>
#include <algorithm>


class Solution53
{
public:
    vector<string> braceExpansionII(string expression)
    {
        unordered_set<string>res;
        queue<string>que;
        que.push(expression);
        while(!que.empty()){
            string str=que.front();
            que.pop();
            if(str.find("{")==string::npos){
                res.insert(str);
                continue;
            }
            int i=0;
            int left=0;
            int right=0;
            while(str[i]!='}'){
                if(str[i]=='{')
                    left=i;
                i++;
            }
            right=i;
            string leftStr=str.substr(0,left);
            string midStr=str.substr(left+1,right-left-1);
            string rightStr="";
            if(right+1<str.size())
               rightStr=str.substr(right+1);
            vector<string>mid=split(midStr,',');
            for(string &m:mid){
                que.push(leftStr+m+rightStr);
            }
        }
        vector<string>ans(res.begin(),res.end());
        sort(ans.begin(),ans.end());
        return ans;
    }


    //因为c++没有split函数，所以需要自己编写一个split
    vector<string> split(string s, char x)
    {
        int n = s.size();
        vector<string> res;
        int L = 0;
        int R = 0;
        while (R < n)
        {
            if (s[R] != x)
                R ++;
            else
            {
                res.push_back(s.substr(L, R - L));
                L = R + 1;
                R = L;
            }
        }
        if (L < R)
            res.push_back(s.substr(L, R - L));
        return res;
    }
};



#endif //LEETCODE_SOLUTION53_H
